#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        if (height.size() < 1) return 0;
        vector<int>idxs(height.size());
        for (int i = 0; i < idxs.size(); ++i)
            idxs[i] = i;
        sort(idxs.begin(), idxs.end(), [&](const int left, const int right) {
            return height[left] < height[right] || (height[left] == height[right] && weight[left] > weight[right]);
            });
        vector<int> dp(idxs.size());
        int len = 0;
        dp[len++] = weight[idxs[0]];
        for (int i = 1; i < weight.size(); ++i) {
            if (weight[idxs[i]] > dp[len - 1]) dp[len++] = weight[idxs[i]];
            else {
                int left = 0, right = len - 1;
                int target = weight[idxs[i]];
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (target <= dp[mid]) right = mid - 1;
                    else left = mid + 1;
                }
                dp[left] = target;
            }
        }
        return len;
    }
};

int main() {
    vector<int> height = { 2868, 5485, 1356, 1306, 6017, 8941, 7535, 4941, 6331, 6181 };
    vector<int> weight = { 5042, 3995, 7985, 1651, 5991, 7036, 9391, 428, 7561, 8594 };
    Solution sol;
    sol.bestSeqAtIndex(height, weight);
}